1. Technical Field
The present invention relates to flash memory and, more particularly, to a system and method for searching a mapping table of a flash memory.
2. Discussion of Related Art
A flash memory may be used as a random access memory (RAM) allowing for data writing and deleting. A flash memory may also be used as a read only memory (ROM) retaining data even when a power is not supplied. In modern portable devices such as digital cameras, personal digital assistants (PDAs), and MP3 players, flash memory is widely used in embedded systems, such as mobile systems, and the like.
Flash memory is considered nonvolatile because it can retain data even after power is disrupted. Unlike a hard disk, flash memory does not allow for the overwriting of existing data in particular sectors. Accordingly, it is necessary to perform an erase of a whole block of data before a write operation may be performed. In storing and accessing data, a logical address may be used to point to data in a logical block. Mapping algorithms may then be used to interpret the logical address and erase, write to and read from data located in physical blocks at physical addresses.
FIG. 1 is a block diagram illustrating a conventional system having a flash memory.
Referring to FIG. 1, a conventional system comprises an external host 10, a host interface 26, a flash memory 30 for storing data, a flash controller 24 for controlling operation of the flash memory, a CPU 22 for controlling general system operation, a work memory 27 as a main memory, and a buffer memory 28. The work memory 27 and the buffer memory 28 may comprise a dynamic random access memory (DRAM) or a static random access memory (SRAM).
In this conventional system, when the host 10 or the CPU 22 requests information from the flash memory, it must know the location of the data in the flash memory. Therefore, a mapping table exists. The mapping table may include a logical-to-physical mapping table, a page mapping table, a sector mapping table, a bad block mapping table, and the like of the flash memory.
The mapping table data is loaded and stored in the work memory 27 when a system is booted by the CPU 22 or the mapping table of the flash memory is changed. Accordingly, the host 10 or the CPU 22 recognizes an address of desired data by referring to the mapping table in order to fetch the data from the flash memory. The mapping table is searched by search software (S/W) residing in the work memory.
However, as the capacity of a flash memory increases, so to does the size and search time of the mapping table. System performance may therefore be degraded. In particular, as applications using high-capacity flash memories, such as flash memory cards or a solid state disks (SSDs), are developed, the mapping table search time is becoming an important issue.